﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    class SieveOfAtkin
    {
        public int Limit;

        bool[] _sieve;
        long[] solution;

        public SieveOfAtkin(int limit)
        {
            if (limit <= 0)
                limit = 5;

            Limit = limit;
            Initialize();
        }

        void Initialize()
        {
            _sieve = new bool[Limit + 1];
            _sieve[2] = true; //2
            _sieve[3] = true; //3
            _sieve[5] = true; //5

            int factor = (int)Math.Sqrt(Limit) + 1;

            for (int x = 1; x <= factor; x++)
            {
                for (int y = 1; y <= factor; y++)
                {
                    int n = 4 * x * x + y * y;
                    if (n <= Limit)
                    {
                        int r = n % 60;

                        if (r == 1 || r == 13 || r == 17 || r == 29 || r == 37 || r == 41 || r == 49 || r == 53)
                            _sieve[n] = !_sieve[n];
                    }

                    n = 3 * x * x + y * y;
                    if (n <= Limit)
                    {
                        int r = n % 60;

                        if (r == 7 || r == 19 || r == 31 || r == 43)
                            _sieve[n] = !_sieve[n];
                    }

                    if (x > y)
                    {
                        n = 3 * x * x - y * y;
                        if (n <= Limit)
                        {
                            int r = n % 60;

                            if (r == 11 || r == 23 || r == 47 || r == 59)
                                _sieve[n] = !_sieve[n];
                        }
                    }
                }
            }


            for (int n = 5; n <= factor; n++)
            {
                if (_sieve[n])
                {
                    for (int j = 1; n * n * j < Limit; j++)
                    {
                        _sieve[n * n * j] = false;
                    }
                }
            }

            List<long> solutionList = new List<long>();

            for(int i = 1; i<=Limit; i++){
                if (_sieve[i])
                    solutionList.Add(i);
            }

            solution = solutionList.ToArray();
            
        }

        public bool IsPrime(long n)
        {
            if (n <= 1)
                return false;

            if (n % 2 == 0 || n % 3 == 0)
                if (n == 2 || n == 3)
                    return true;
                else
                    return false;

            if (n <= Limit)
            {
                return _sieve[n];
            }

            double limit = Math.Sqrt(n);
            if (limit == (long)limit)
                return false;

            foreach (long prime in solution)
            {
                if (n % prime == 0)
                    return false;

                if (prime > limit)
                    break;
            }

            //for (long k = 1; 6 * k + 1 <= Limit && 6 * k - 1 < limit; k++)
            //{
            //    if (_sieve[6 * k + 1])
            //        if (n % (6 * k + 1) == 0)
            //            return false;
            //    if (_sieve[6 * k - 1])
            //        if (n % (6 * k - 1) == 0)
            //            return false;
            //}


            long initial = Limit - Limit % 6 ;

            for (long k = initial; k - 1 < limit; k+=6)
            {
                if (n % (k + 1) == 0 || n % (k - 1) == 0)
                    return false;
            }

            return true;
        }
    }
}
